#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 简单的暴力匹配方法
int search(string s, string p) {
    int n = 0;
    for (int i = 0; i < s.size() - p.size(); i++) {
        bool match = true;
        for (int j = 0; j < p.size(); j++) {
            if (s[i + j]!= p[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            cout << "匹配位置：" << i << endl;
            n++;
        }
    }
    cout << "共找到" + to_string(n) + "个结果" << endl;
    return n;
}

// KMP算法实现：构建next数组
vector<int> buildNext(string s) {
    vector<int> next(s.size());
    next[0] = -1;
    for (int i = 1; i < s.size(); i++) {
        int nexti = next[i - 1] + 1;
        while (nexti >= 0 && s[nexti]!= s[i])
            nexti = nexti > 0? next[nexti - 1] + 1 : -1;
        next[i] = nexti;
    }
    return next;
}

// 使用KMP算法进行字符串匹配
int searchKMP(string s, string p) {
    vector<int> next = buildNext(p);
    int j = 0;
    for (int i = 0; i < s.size(); i++) {
        while (j >= 0 && s[i]!= p[j]) {
            if (j == 0)
                j = -1;
            else
                j = next[j - 1] + 1;
        }
        if (++j == p.size())
            return i - j + 1;
    }
    return -1;
}

int main() {
    string s = "ababaababcb", p = "ababc";
    int ans = searchKMP(s, p);
    cout << "匹配的下标位置为: " << ans << endl;
    return 0;
}